#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *这道题⽬还可以继续深化，就是⼀步⼀个台阶，两个台阶，三个台阶，直到 m个台阶，有多少种⽅法爬
到n阶楼顶。
这⼜有难度了，这其实是⼀个完全背包问题，但⼒扣上没有这种题⽬，所以后续我在讲解背包问题的时
候，今天这道题还会拿从背包问题的⻆度上来再讲⼀遍。
 * */
//

int climbStairs(int n) {
    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) { // 把m换成2，就可以AC爬楼梯这道题
            if (i - j >= 0) dp[i] += dp[i - j];
        }
    }
    return dp[n];
}